#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType *elem; //整形指针，申请的堆空间起始地址存入elem
    int TableLen;   //存储动态数组里边元素的个数
}SSTable;

//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
//打印顺序表
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//交换两个元素
void swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
//排序往往都是两层循环
//优先去写内层循环，再写外层循环
void BubbleSort(ElemType *elem,int len)
{
    bool flag; //哨兵
    for (int i = 0; i < len-1; i++) {      //控制的是有序数的数目
        flag=false; //元素是否发生交换的标志
        for (int j = len-1; j > i; j--) {  //内层控制比较和交换
            if(elem[j-1]>elem[j])
            {
                swap(elem[j-1],elem[j]);
                flag=true;
            }
        }
        if(false==flag) //如何一趟比较没有发生任何交换，说明数组有序，提前结束排序
            return;
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);
//    ElemType A[10]={64,94,95,79,69,84,18,22,12,78};
//    //内存copy接口，当你copy整型数组，或者浮点型时，使用memcpy，不能用strcpy，初试考memcpy概率很低
//    memcpy(ST.elem,A, sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    ST_Print(ST);
    BubbleSort(ST.elem,10);
    ST_Print(ST);
    return 0;
}
